/*
 * Indice.cpp
 */

#include "Indice.h"

Indice::Indice(string nombre, int tamBloque) {
	this->archivoBloques = new ArchivoDeBloques(nombre, tamBloque);

}

Indice::Indice(string nombre) {
	this->archivoBloques = new ArchivoDeBloques(nombre);
}

Indice::~Indice() {
}

int Indice::escribirNodoHoja(NodoHoja nodo) {

	nodo.guardarEnBloque(this->archivoBloques->tamBloque);
	this->archivoBloques->agregarBloquesVacios(1);
	this->archivoBloques->escribirBloque(nodo.bloque, nodo.numeroDeNodo);
}

int Indice::escribirNodoInterno(NodoInterno nodo) {

	nodo.guardarEnBloque(this->archivoBloques->tamBloque);
	this->archivoBloques->agregarBloquesVacios(1);
	this->archivoBloques->escribirBloque(nodo.bloque, nodo.numeroDeNodo);
}

Bloque * Indice::leerNodo(int numeroNodo) {

	return (this->archivoBloques->leerBloque(numeroNodo));
}

ResultadoBuscar Indice::buscar(int clave) {
	int raiz = 0;
	int nodoPadre = -1;
	return (buscarClaveInterno(clave, raiz, nodoPadre));
}

ResultadoBuscar Indice::buscarClaveInterno(int clave, int numNodo,
		int numNodoPadre) {

	NodoInterno nodoInterno;
	NodoHoja nodoHoja;

	Bloque * bloque = leerNodo(numNodo);

	//Verifica si es hoja o interno.
	int esHoja = nodoHoja.leerDeBloque(*bloque);

	if (esHoja != -1) {
		//Es una hoja y busca la clave entre sus elementos.
		if (nodoHoja.tieneClave(clave)) {
			ResultadoBuscar resultado(true, nodoHoja.numeroDeNodo,
					numNodoPadre);
			return resultado;
		} else {
			ResultadoBuscar resultado(false, nodoHoja.numeroDeNodo,
					numNodoPadre);
			return resultado;
		}

	} else {

		//Es interno y decide hacia que hijo continuar la busqueda
		nodoInterno.leerDeBloque(*bloque);

		for (int i = 0; i < nodoInterno.elementos.size(); i++) {
			if (clave < nodoInterno.elementos.at(i).clave) {
				if (i == 0) {
					return (buscarClaveInterno(clave, nodoInterno.hijoIzq,
							nodoInterno.numeroDeNodo));
				} else {
					return (buscarClaveInterno(clave,
							nodoInterno.elementos.at(i - 1).hijoDer,
							nodoInterno.numeroDeNodo));
				}
				break;
			}
		}
		return (buscarClaveInterno(clave,
				nodoInterno.elementos.at(nodoInterno.elementos.size() - 1).hijoDer,
				nodoInterno.numeroDeNodo));
	}

}


vector<ElementoHoja> Indice::recorreOrdenado(){

	vector<ElementoHoja> vectorE;

	NodoInterno nodoInterno;
	NodoHoja nodoHoja;

	//leo la raiz

	Bloque * bloque = leerNodo(0);
	if (archivoBloques->cantBloques == 0){
	               return vectorE;
	}

	nodoInterno.leerDeBloque(*bloque);
	nodoHoja.leerDeBloque(*bloque);
	//Verifica si es hoja o interno.
	int esHoja = nodoHoja.leerDeBloque(*bloque);
	int esInterno = nodoInterno.leerDeBloque(*bloque);
	//cout<<"esHoja"<<esHoja<<"es interno"<<esInterno<<endl;
	if ((esHoja==0) or (esInterno==0)){
	int bloqueActual=0;
	//si es interno me muevo a la hoja
	while (esHoja == -1) {

		bloqueActual=nodoInterno.hijoIzq;
		bloque = leerNodo(bloqueActual);
		nodoInterno.leerDeBloque(*bloque);
		esHoja = nodoHoja.leerDeBloque(*bloque);
	}
	//me muevo para los nodos proximos mientras no llegue al final del arbol
	while (bloqueActual!= -1){

		nodoHoja.leerDeBloque(*bloque);

		for (unsigned int i = 0; i < nodoHoja.elementos.size(); i++) {
			vectorE.push_back(nodoHoja.elementos.at(i));
		}
		bloqueActual=nodoHoja.proximoNodo;
		bloque = leerNodo(bloqueActual);

	}
	}
	return vectorE;

}

int Indice::guardarNodosLibres(string nombreArch) {
	std::ofstream FILE(nombreArch.c_str(),
			std::ios::out | std::ofstream::binary);
	std::copy(nodosLibres.begin(), nodosLibres.end(),
			std::ostreambuf_iterator<char>(FILE));
}

int Indice::cargarNodosLibres(string nombreArch) {
	std::ifstream INFILE(nombreArch.c_str(),
			std::ios::in | std::ifstream::binary);
	std::vector<int> data((std::istreambuf_iterator<char>(INFILE)),
			std::istreambuf_iterator<char>());
	nodosLibres = data;
}

int Indice::modificar(ElementoHoja elementoClaveValor) {
	ResultadoBuscar resultadoBuscar = buscar(elementoClaveValor.clave);

	if (resultadoBuscar.encontrado) {
		NodoHoja nodoHoja;
		Bloque * bloque = leerNodo(resultadoBuscar.numeroDeNodo);
		nodoHoja.leerDeBloque(*bloque);
		return modificarInterno(nodoHoja, elementoClaveValor);
	} else {
		return -1;

	}
}

ElementoHoja Indice::buscarElemento(int clave) {
	ResultadoBuscar resultadoBuscar = buscar(clave);

	if (resultadoBuscar.encontrado) {
		NodoHoja nodoHoja;
		Bloque * bloque = leerNodo(resultadoBuscar.numeroDeNodo);
		nodoHoja.leerDeBloque(*bloque);
		vector<ElementoHoja> velemh = nodoHoja.elementos;
		for(unsigned int i=0;i<velemh.size();i++){
			ElementoHoja elem=velemh.at(i);
			if (elem.clave==clave)
				return elem;
		}
	}
	ElementoHoja elem(-1,"");
	return elem;
}

int Indice::baja(int clave) {
	ResultadoBuscar resultadoBuscar = buscar(clave);

	if (resultadoBuscar.encontrado) {
		NodoHoja nodoHoja;
		Bloque * bloque = leerNodo(resultadoBuscar.numeroDeNodo);
		nodoHoja.leerDeBloque(*bloque);
		return bajaInterna(nodoHoja, clave);
	} else {
		return -1;

	}
}

int Indice::bajaInterna(NodoHoja nodo, int clave) {

	int posElemento= -1;
	for (int i = 0; i < nodo.elementos.size(); i++) {
		if (clave == nodo.elementos.at(i).clave) {
			posElemento = i;
			break;
		}
	}

	if (posElemento == -1){
		return -1;
	}
	nodo.elementos.erase (nodo.elementos.begin() + posElemento);
	//Vuelve a escribir el nodo con el valor actualizado.
	return sobrescribirNodoHoja(nodo);
}

int Indice::modificarInterno(NodoHoja nodo, ElementoHoja elementoClaveValor) {

	for (int i = 0; i < nodo.elementos.size(); i++) {
		if (elementoClaveValor.clave == nodo.elementos.at(i).clave) {
			nodo.elementos.at(i).valor = elementoClaveValor.valor;
			break;
		}
	}
	//Vuelve a escribir el nodo con el valor actualizado.
	return sobrescribirNodoHoja(nodo);
}

int Indice::sobrescribirNodoHoja(NodoHoja nodo) {

	int res = nodo.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}
	this->archivoBloques->escribirBloque(nodo.bloque, nodo.numeroDeNodo);

	return 0;
}

int Indice::sobrescribirNodoInterno(NodoInterno nodo) {

	int res = nodo.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}
	this->archivoBloques->escribirBloque(nodo.bloque, nodo.numeroDeNodo);

	return 0;
}

int Indice::alta(ElementoHoja elemento) {
	ResultadoBuscar resultadoBuscar = buscar(elemento.clave);
	if (resultadoBuscar.encontrado) {
		return -1;
	} else {
		//Da de alta el elemento
		NodoHoja nodoHoja;
		Bloque * bloque = leerNodo(resultadoBuscar.numeroDeNodo);
		nodoHoja.leerDeBloque(*bloque);

		if (nodoHoja.numeroDeNodo == 0) {
			nodoHoja.proximoNodo = -1;
		}
		nodoHoja.elementos.push_back(elemento);
		sort(nodoHoja.elementos.begin(), nodoHoja.elementos.end());

		int res = nodoHoja.guardarEnBloque(this->archivoBloques->tamBloque);
		if (res == -1) {
			if (nodoHoja.numeroDeNodo == 0) {
				return resolverOverflowRaiz(nodoHoja);
			}
			return resolverOverflowHoja(nodoHoja,
					resultadoBuscar.numeroDeNodoPadre);
		}
		//Si no esta la raiz se crea
		if (archivoBloques->cantBloques == 0) {
			archivoBloques->agregarBloquesVacios(1);
		}
		this->archivoBloques->escribirBloque(nodoHoja.bloque,
				nodoHoja.numeroDeNodo);

		return 0;
	}
}

int Indice::resolverOverflowHoja(NodoHoja nodoHoja, int numNodoPadre) {
	int res = 0;

	int par = (nodoHoja.elementos.size() % 2) == 0;
	int mitad;

	if (par) {
		mitad = (nodoHoja.elementos.size() / 2);
	} else {
		mitad = ((nodoHoja.elementos.size() / 2) + 1);
	}

	std::vector<ElementoHoja> elementosIzq;
	std::vector<ElementoHoja> elementosDer;

	for (int i = 0; i < mitad; i++) {
		elementosIzq.push_back(nodoHoja.elementos.at(i));
	}

	for (int i = mitad; i < nodoHoja.elementos.size(); i++) {
		elementosDer.push_back(nodoHoja.elementos.at(i));
	}

	NodoHoja nodoNuevo;
	nodoNuevo.elementos = elementosDer;
	nodoNuevo.proximoNodo = nodoHoja.proximoNodo;
	nodoNuevo.nivel = 0;
	NodosId ids;
	int numeroNodoDisponible = ids.obtenerIdNodo();
	ids.incrementarIdNodo();
	nodoNuevo.numeroDeNodo = numeroNodoDisponible;
	res = nodoNuevo.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}

	nodoHoja.elementos = elementosIzq;
	nodoHoja.proximoNodo = nodoNuevo.numeroDeNodo;
	res = nodoHoja.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}

	int claveSube = elementosDer.at(0).clave;
	int numNodoSube = nodoNuevo.numeroDeNodo;

	res = altaEnNodoInterno(numNodoPadre, claveSube, numNodoSube);
	if (res == -1) {
		return res;
	}

	//Si lo anterior se pudo guardar, se guardan tambien las hojas
	this->archivoBloques->escribirBloque(nodoHoja.bloque,
			nodoHoja.numeroDeNodo);

	archivoBloques->agregarBloquesVacios(1);
	this->archivoBloques->escribirBloque(nodoNuevo.bloque,
			nodoNuevo.numeroDeNodo);

	return res;
}

int Indice::resolverOverflowRaiz(NodoHoja nodoHoja) {
	int res = 0;

	int par = (nodoHoja.elementos.size() % 2) == 0;
	int mitad;

	if (par) {
		mitad = (nodoHoja.elementos.size() / 2);
	} else {
		mitad = ((nodoHoja.elementos.size() / 2) + 1);
	}

	std::vector<ElementoHoja> elementosIzq;
	std::vector<ElementoHoja> elementosDer;

	for (int i = 0; i < mitad; i++) {
		elementosIzq.push_back(nodoHoja.elementos.at(i));
	}

	for (int i = mitad; i < nodoHoja.elementos.size(); i++) {
		elementosDer.push_back(nodoHoja.elementos.at(i));
	}

	NodoHoja nodoNuevoDer;
	nodoNuevoDer.elementos = elementosDer;
	nodoNuevoDer.proximoNodo = -1;
	nodoNuevoDer.nivel = 0;
	//Como recien empieza a armar la raiz no hay nodos libres de antemano
	nodoNuevoDer.numeroDeNodo = 2;
	//Si no entra en el nodo devuelve error
	res = nodoNuevoDer.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}

	NodoHoja nodoNuevoIzq;
	nodoNuevoIzq.elementos = elementosIzq;
	nodoNuevoIzq.proximoNodo = nodoNuevoDer.numeroDeNodo;
	nodoNuevoIzq.nivel = 0;
	//Como recien empieza a armar la raiz no hay nodos libres de antemano
	nodoNuevoIzq.numeroDeNodo = 1;
	//Si no entra en el nodo devuelve error
	res = nodoNuevoIzq.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}

	int claveSube = elementosDer.at(0).clave;

	ElementoInterno interno(claveSube, nodoNuevoDer.numeroDeNodo);
	NodoInterno nodoInterno;
	nodoInterno.numeroDeNodo = 0;
	nodoInterno.nivel = 1;
	nodoInterno.hijoIzq = nodoNuevoIzq.numeroDeNodo;
	std::vector<ElementoInterno> elementos;
	elementos.push_back(interno);
	nodoInterno.elementos = elementos;
	nodoInterno.cantidadDeElementos = nodoInterno.elementos.size();

	//Si no entra en el nodo devuelve error
	res = sobrescribirNodoInterno(nodoInterno);
	if (res == -1) {
		return res;
	}
	//Si lo anterior se pudo guardar, se guardan tambien las hojas
	archivoBloques->agregarBloquesVacios(1);
	this->archivoBloques->escribirBloque(nodoNuevoIzq.bloque,
			nodoNuevoIzq.numeroDeNodo);
	archivoBloques->agregarBloquesVacios(1);
	this->archivoBloques->escribirBloque(nodoNuevoDer.bloque,
			nodoNuevoDer.numeroDeNodo);

	//Actualiza la secuencia de id de nodo; el 0, 1 y 2 se usaron en este metodo.
	NodosId ids;
	ids.inicializarIdNodo(3);

	return res;
}

int Indice::altaEnNodoInterno(int numNodo, int clave, int numNodoSube) {
	int res = 0;

	NodoInterno nodoInterno;
	Bloque * bloque = leerNodo(numNodo);
	nodoInterno.leerDeBloque(*bloque);

	ElementoInterno elemento;
	elemento.clave = clave;
	elemento.hijoDer = numNodoSube;

	nodoInterno.elementos.push_back(elemento);
	sort(nodoInterno.elementos.begin(), nodoInterno.elementos.end());

	res = sobrescribirNodoInterno(nodoInterno);
	if (res == -1) {
		int numNodoPadre = obtenerPadreDeNodoInterno(nodoInterno.numeroDeNodo);
		if (numNodoPadre == -1) {
			return resolverOverflowInternoRaiz(nodoInterno);
		} else {
			return resolverOverflowInterno(nodoInterno, numNodoPadre);
		}
	}
	return res;
}

int Indice::resolverOverflowInterno(NodoInterno nodoInterno, int numNodoPadre) {
	int res = 0;

	int mitad = (nodoInterno.elementos.size() / 2);

	std::vector<ElementoInterno> elementosIzq;
	std::vector<ElementoInterno> elementosDer;

	for (int i = 0; i < mitad; i++) {
		elementosIzq.push_back(nodoInterno.elementos.at(i));
	}

	for (int i = mitad + 1; i < nodoInterno.elementos.size(); i++) {
		elementosDer.push_back(nodoInterno.elementos.at(i));
	}

	int claveSube = nodoInterno.elementos.at(mitad).clave;
	int hijoIzqNodoDerecho = nodoInterno.elementos.at(mitad).hijoDer;

	NodoInterno nodoNuevo;
	nodoNuevo.elementos = elementosDer;
	nodoNuevo.nivel = nodoInterno.nivel;
	nodoNuevo.hijoIzq = hijoIzqNodoDerecho;
	NodosId ids;
	int numeroNodoDisponible = ids.obtenerIdNodo();
	ids.incrementarIdNodo();
	nodoNuevo.numeroDeNodo = numeroNodoDisponible;
	res = nodoNuevo.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}

	nodoInterno.elementos = elementosIzq;
	res = nodoInterno.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}

	int numNodoSube = nodoNuevo.numeroDeNodo;

	res = altaEnNodoInterno(numNodoPadre, claveSube, numNodoSube);
	if (res == -1) {
		return res;
	}

	//Si lo anterior se pudo guardar, se guardan tambien las hojas
	this->archivoBloques->escribirBloque(nodoInterno.bloque,
			nodoInterno.numeroDeNodo);

	archivoBloques->agregarBloquesVacios(1);
	this->archivoBloques->escribirBloque(nodoNuevo.bloque,
			nodoNuevo.numeroDeNodo);

	return res;

}

int Indice::obtenerPadreDeNodoInterno(int numNodoInterno) {

	NodosId ids;
	int cantidadNodos = ids.obtenerIdNodo();
	NodoInterno nodoInterno;

	for (int i = 0; i < cantidadNodos; i++) {

		Bloque * bloque = leerNodo(i);
		//Verifica si es hoja o interno.
		int esInterno = nodoInterno.leerDeBloque(*bloque);
		if (esInterno != -1) {
			if (nodoInterno.hijoIzq == numNodoInterno) {
				return nodoInterno.numeroDeNodo;
			} else {
				for (int j = 0; j < nodoInterno.elementos.size(); j++) {
					if (nodoInterno.elementos.at(j).hijoDer == numNodoInterno) {
						return nodoInterno.numeroDeNodo;
					}
				}
			}
		}
	}
	//Si llego hasta aca es porque no lo encontro
	return -1;
}

int Indice::resolverOverflowInternoRaiz(NodoInterno nodoInterno) {
	int res = 0;

	int mitad = (nodoInterno.elementos.size() / 2);

	std::vector<ElementoInterno> elementosIzq;
	std::vector<ElementoInterno> elementosDer;

	for (int i = 0; i < mitad; i++) {
		elementosIzq.push_back(nodoInterno.elementos.at(i));
	}

	for (int i = mitad + 1; i < nodoInterno.elementos.size(); i++) {
		elementosDer.push_back(nodoInterno.elementos.at(i));
	}

	int claveSube = nodoInterno.elementos.at(mitad).clave;
	int hijoIzqNodoDerecho = nodoInterno.elementos.at(mitad).hijoDer;

	NodoInterno nodoNuevoDer;
	nodoNuevoDer.elementos = elementosDer;
	nodoNuevoDer.nivel = nodoInterno.nivel;
	nodoNuevoDer.hijoIzq = hijoIzqNodoDerecho;

	NodosId idsNodos;
	int numeroNodoDisponible = idsNodos.obtenerIdNodo();
	idsNodos.incrementarIdNodo();
	nodoNuevoDer.numeroDeNodo = numeroNodoDisponible;

	//Si no entra en el nodo devuelve error
	res = nodoNuevoDer.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}

	NodoInterno nodoNuevoIzq;
	nodoNuevoIzq.elementos = elementosIzq;
	nodoNuevoIzq.nivel = nodoInterno.nivel;
	numeroNodoDisponible = idsNodos.obtenerIdNodo();
	idsNodos.incrementarIdNodo();
	nodoNuevoIzq.numeroDeNodo = numeroNodoDisponible;
	nodoNuevoIzq.hijoIzq = nodoInterno.hijoIzq;

	//Si no entra en el nodo devuelve error
	res = nodoNuevoIzq.guardarEnBloque(this->archivoBloques->tamBloque);
	if (res == -1) {
		return res;
	}

	ElementoInterno interno(claveSube, nodoNuevoDer.numeroDeNodo);
	NodoInterno nodoInternoNuevo;
	nodoInternoNuevo.numeroDeNodo = nodoInterno.numeroDeNodo;
	nodoInternoNuevo.nivel = nodoInterno.nivel + 1;
	nodoInternoNuevo.hijoIzq = nodoNuevoIzq.numeroDeNodo;
	std::vector<ElementoInterno> elementos;
	elementos.push_back(interno);
	nodoInternoNuevo.elementos = elementos;
	nodoInternoNuevo.cantidadDeElementos = nodoInterno.elementos.size();

	//Si no entra en el nodo devuelve error
	res = sobrescribirNodoInterno(nodoInternoNuevo);
	if (res == -1) {
		return res;
	}
	//Si lo anterior se pudo guardar, se guardan tambien las hojas
	archivoBloques->agregarBloquesVacios(1);
	this->archivoBloques->escribirBloque(nodoNuevoIzq.bloque,
			nodoNuevoIzq.numeroDeNodo);
	archivoBloques->agregarBloquesVacios(1);
	this->archivoBloques->escribirBloque(nodoNuevoDer.bloque,
			nodoNuevoDer.numeroDeNodo);

	return res;
}
